// 无经验的 少经验的程序结构  算法 容易导致 产生 bug, 写出结构   易漏边界
// 时时熟悉 以降低bug概率

// 结构为 while{if if elif}
int binary(std::vector<int> vec, int target) {
  int left = 0;
  int right = vec.size() - 1;
  int mid = (left + right) / 2;  // 1. mid的计算
  while (left <= right) {        // 2. while + 跳出条件

    if (vec[mid] < target) {
      left = mid + 1;

    } else if (vec[mid] > target) {
      right = mid - 1;
    } else {
      return mid;
    }
    mid = (left + right) / 2;  // 3.  mid的更新
  }
}

// 结构为 for { for { if } }
void bubble(vector<int>& vec) {
  for (size_t i = 0; i < vec.size() - 1;
       i++)  //  1 嵌套for的条件    i 0   ---------->   < vec.size() - 1
             // j i + 1-----------> vec.size()
  {
    for (size_t j = i + 1; j < vec.size(); j++)  // 2
    {
      if (vec[i] > vec[j]) {
        int temp = vec[j];
        vec[j] = vec[i];
        vec[i] = temp;
      }
    }
  }
}

//结构为 for { if + while }
void front_insert(vector<int>& vec) {
  for (int i = 1; i < vec.size(); i++) {
    if (vec[i] > vec[i - 1]) continue;

    int temp = vec[i];

    int j = i;  // 注意要重新赋值index 不然会修改之前的i
    while (
        j >= 1 &&
        vec[j - 1] >
            temp) {  // <= 可能涉及稳定性问题  注意j>=1
                     // 放在前面以及j应该等于多少  注意比较的是有序数组与temp，
      vec[j] = vec[j - 1];
      j--;
    }

    vec[j] = temp;  //注意最后对temp的恢复
  }
}

// fast_sort  单次排序代码，非递归可以用栈存储需要单次排序的所有index范围，
//结构为 while{ if }
//前后指针法顾名思义就是借助前后2个指针进行排序。排序的主要思路：我们这里以end作为key值，同时定义2个指针(下标)，前指针cur和后指针prev。当cur对应的值小于key的时候，先让prev++，然后再交换prev和cur对应的值，最后cur再++；如果cur对应的值大于key，只让cur++。这样做可以让小于等于key的值永远在prev的前面，prev和cur中间的值都是大于key的

int core(vector<int>& arr, int left, int right) {
  int pre = 0;  //注意值的初始化
  int curr = 0;
  int key = arr[right];  //这里的right注意，不能等于arr的size
  while (curr <= right) {
    if (arr[curr] <= key) {
      std::swap(arr[pre], arr[curr]);
      pre++;  //注意是在if里进行pre++
    }
    curr++;
  }
  return pre;  // right begin index
}
